package me.mingshan.leetcode;

/**
 * @author hanjuntao
 * @date 2025/10/3 0003
 */
public class L_606_根据二叉树创建字符串 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        root.left = node1;
        root.left.right = node2;
        root.right = node3;
        System.out.println(tree2str(root)); // 1(2()(4))(3)

        // ----------------------
        TreeNode root2 = new TreeNode(1);
        TreeNode node21 = new TreeNode(2);
        TreeNode node22 = new TreeNode(3);
        TreeNode node23 = new TreeNode(4);

        root2.left = node21;
        root2.left.left = node22;
        root2.left.right = node23;
        System.out.println(tree2str(root2)); //1(2(3)(4))
    }

    /**
     * 题意：
     * <p>
     * 题目的意思是子节点需要用()来包裹。举例来说，二叉树[root,left,right]，则转换为root(left)(right)。
     * 如果只有left为空节点，则输出root()(right)；如果只有right为空节点则可以忽略右节点的()，输出为root(left)。
     * <p>
     * 思路：
     * <p>
     * 1. 递归遍历二叉树
     * 2. 拼接当前节点的值
     * 3. 判断子节点如何拼接
     * 3.1 如果只存在右节点，左节点为空，则需要拼接()
     * 3.2 如果存在左节点，则正常拼接(dfs(root.left))
     * 3.3 如果存在右节点，则正常拼接(dfs(root.right))
     *
     * @param root
     * @return
     */
    public static String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }

    private static void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        sb.append(node.val);

        // 如果只存在右节点，需要添加()
        if (node.left == null && node.right != null) {
            sb.append("()");
        }

        // 如果存在左节点，则正常拼接
        if (node.left != null) {
            sb.append("(");
            dfs(node.left, sb);
            sb.append(")");
        }

        // 存在右节点
        if (node.right != null) {
            sb.append("(");
            dfs(node.right, sb);
            sb.append(")");
        }
    }

}
